class Solution {
    boolean[] visited;
    int count;
    int time;
    List<List<Pair<Integer, Integer>>> edges;
    Map<Integer, Integer> nodeTime;
    int[] distance;

    public int networkDelayTime(int[][] times, int n, int k) {
        // return byBFS(times, n, k);     
        // return byBellManFord(times, n, k);   
        return byDijkstra(times, n, k);
    }
    private int byDijkstra(int[][] times, int n, int k) {
        visited = new boolean[n+1];
        distance = new int[n+1];
        Arrays.fill(distance, (int)1e9);
        distance[k] = 0;
        edges = new ArrayList<>();
        for (int i = 0; i < visited.length; i++) {
            edges.add(new ArrayList<>());
        }
        for (int i = 0; i < times.length; i++) {
            int x = times[i][0];
            int y = times[i][1];
            int z = times[i][2];
            this.edges.get(x).add(new Pair<>(y, z));
        }
        Queue<Pair<Integer, Integer>> queue = new PriorityQueue<>(n, (pair1, pair2) -> pair1.getValue() - pair2.getValue());
        queue.offer(new Pair<>(k, distance[k]));
        while (!queue.isEmpty()) {
            Integer topVal = queue.poll().getKey();
            if (visited[topVal]) continue;
            visited[topVal] = true;
            for (Pair<Integer, Integer> pair : edges.get(topVal)) {
                int val = pair.getKey();
                int time = pair.getValue();
                if (distance[topVal] + time < distance[val]) {
                    distance[val] = distance[topVal] + time;
                    queue.offer(new Pair<>(val, distance[val]));
                }
            }
        }
        int ans = 0;
        for (int i = 1; i < distance.length; i++) {
            ans = Math.max(ans, distance[i]);
        }
        if (ans == 1e9) ans = -1;
        return ans;
    }
    private int byBellManFord(int[][] times, int n, int k) {
        int[] ans = new int[n+1];
        Arrays.fill(ans, (int)1e9);
        ans[k] = 0;
        for (int i = 0; i < n; i++) {
            boolean swaped = false;
            for (int j = 0; j < times.length; j++) {
                int[] time = times[j];
                int x = time[0];
                int y = time[1];
                int z = time[2];
                if (ans[x] + z < ans[y]) {
                    ans[y] = ans[x] + z;
                    swaped = true;
                }
            }
            if (!swaped) break;
        }
        int result = -1;
        for (int i = 1; i < ans.length; i++) {
            result = Math.max(result, ans[i]);
        }
        if (result == 1e9) result = -1;
        return result;
    }
    private int byBFS(int[][] times, int n, int k) {
        count = n + 1;
        visited = new boolean[count];
        time = 0;
        edges = new ArrayList<>();
        nodeTime = new HashMap<>();
        for (int i = 0; i < count; i++) {
            edges.add(new ArrayList<>());
            nodeTime.put(i, 1000);
        }
        nodeTime.put(0, 0);
        for (int i = 0; i < times.length; i++) {
            addEdge(times[i][0], times[i][1], times[i][2]);
        }
        bfs(k);
        time = nodeTime.entrySet()
                       .stream()
                       .map(i -> i.getValue())
                       .max(Comparator.comparingInt(a -> a))
                       .orElse(-1);
        if (time == 1000) {
            time = -1;
        }
        return time;
    }
    private void addEdge(int x, int y, int time) {
        this.edges.get(x).add(new Pair(y, time));
    }
    private void bfs(int k) {
        Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair(k, 0));
        visited[k] = true;
        while (!queue.isEmpty()) {
            Pair<Integer, Integer> top = queue.poll();
            int topValue = top.getKey();
            int topTime = top.getValue();
            int oldTime = nodeTime.get(topValue);
            if (topTime < oldTime) {
                nodeTime.put(topValue, topTime);
            }
            for (Pair<Integer, Integer> pair : edges.get(topValue)) {
                int value = pair.getKey();
                int time = pair.getValue();
                int newTime = time + topTime;
                if (!visited[value]) {
                    queue.offer(new Pair(value, newTime));
                    visited[value] = true;
                } else {
                    if (newTime < nodeTime.get(value)) {
                        nodeTime.put(value, newTime);
                        queue.offer(new Pair(value, newTime));
                    }
                }
            }
        }
    }
}
